# Knapsack.py
# 基于背包问题的加密算法
# -*- coding: utf-8 -*-
"""
Created on 2021

@author: Ximing
"""

import itertools
import copy
import random

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


def create_pubkey(data,m,w):
    for i in range(len(data)):
        data[i] = data[i] * w

    for j in range(len(data)):
        data[j] = data[j] % m
    return data


# 将二进制数据进行加密
def encryp(clear_txt, pubkey):
    # 定义 密文列表
    cipher_list = []
    resul_list = []
    r=0
    cipher = 0
    for i in range(len(clear_txt)):
        if i % 8 == 0 and i != 0:
            cipher = sum(cipher_list)
            resul_list.append(cipher)
            cipher_list = []
            r=r+1
        if clear_txt[i] == 1:
            cipher_list.append(clear_txt[i] * pubkey[i%8])
    # 密文的值
    cipher = sum(cipher_list)
    resul_list.append(cipher)
    return resul_list


# 将加密后的数据进行解密
def dec(cipher, input_list, m, w):
    result_list =[]
    for i in range(len(cipher)):
        dec = decryption(cipher[i], input_list, m, w)
        result_list.append(dec)
    return result_list

def decryption(cipher, input_list, m, w):
    # 私钥序列和
    inv_w = ModReverse(w, m)
    sumx = 0
    # for i in cipher:
    sumx = (inv_w * cipher) % m
    # for k in range(len(input_list)):
    result_list = []
    clear_list = []
    for s in range(0, 7):
        for p in itertools.combinations(input_list, s):
            if sum(list(p)) == sumx:
                result_list = list(p)
    # print(result_list)
    for l in input_list:
        if l in result_list:
            clear_list.append(1)
        else:
            clear_list.append(0)
    result_l = []
    for t in clear_list:
        result_l.append(t)
    return result_l


# 下面两个函数是用来求乘法逆元的
def EX_GCD(a, b, arr):  # 扩展欧几里得
    if b == 0:
        arr[0] = 1
        arr[1] = 0
        return a
    g = EX_GCD(b, a % b, arr)
    t = arr[0]
    arr[0] = arr[1]
    arr[1] = t - int(a / b) * arr[1]
    return g


def ModReverse(a, n):  # ax=1(mod n) 求a模n的乘法逆x
    arr = [0, 1, ]
    gcd = EX_GCD(a, n, arr)
    if gcd == 1:
        return (arr[0] % n + n) % n
    else:
        return -1

def sumlist(list):
    sum = 0
    for i in list:
        sum = sum + i
    return sum

def tobits(s):
    result = []
    for c in s:
        bits = bin(ord(c))[2:]
        bits = '00000000'[len(bits):] + bits
        result.extend([int(b) for b in bits])
    return result

def tostr(dec):
    resulstr=[]
    for bits in dec:
        char = frombits(bits)
        resulstr.append(char)
    return resulstr

def frombits(bits):
    byte =0
    count =0
    for i in bits:
        byte =byte+ bits[i]*(2**(7-count))
        count = count +1
    return chr(byte)

def gen_Siks(n):
    rs = []
    for i in range(0, n):
        n = random.randint(11, 135)
        if i == 0:
            rs.append(n)
        else:
            s = sumlist(rs)
            n = s + random.randint(11, 3110)
            rs.append(n)
    s = sumlist(rs)
    m = s + random.randint(120, 520)
    w = 2
    for i in range(5, m):
        if gcd(i, m) == 1:
            w = i
            break
    return rs, m, w

if __name__ == "__main__":
    # 将函数生成的超递增序列进行赋值
    SuperIKS, m, w = gen_Siks(8)
    pri_key = copy.deepcopy(SuperIKS)
    print('the super increasing sequence is : ', SuperIKS)

    pubkey= create_pubkey(SuperIKS, m, w)
    print('the public key is:', pubkey)
    print('the private key:( m and w is)', m,  w)
    print('( pri_key)=', pri_key)

    plaintxt= "AloveBob"
    print('the plain text is: ', plaintxt)
    bit_plaintxt = tobits(plaintxt)
    print('the bits of plain text is: ')
    for i in range(len(bit_plaintxt)):
        if(i==0):
            print("[",end="")
        print(bit_plaintxt[i], end="")
    print("]")
    cipher = encryp(bit_plaintxt, pubkey)

    print('\nthe encrypted information is: ', cipher)

    plaintxt_dec = dec(cipher, pri_key, m, w)
    print('the decrypted plain bits is : ',end=" ")
    for i in range(len(plaintxt_dec)):
        if(i%3==0):
            print("\n")
        print(plaintxt_dec[i], end=",")
    print("\n")
    print('the decrypted text is :', tostr(plaintxt_dec))

